/*
 * @lc app=leetcode.cn id=1367 lang=typescript
 *
 * [1367] 二叉树中的列表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

// 比较是否有全匹配路径
function judge(head: ListNode | null, root: TreeNode | null): boolean {
  // 找到了全匹配路径
  if (head === null) return true;
  // root为null，head还有节点，肯定不是全匹配路径
  if (root === null) return false;
  // 匹配路径过程中，有不同节点
  if (root.val !== head.val) return false;
  // 递归比较左右节点和下一个链表节点
  return judge(head.next, root.left) || judge(head.next, root.right);
}

// 递归寻找相同的第一个节点
function isSubPath(head: ListNode | null, root: TreeNode | null): boolean {
  // head是空链表，肯定能找到路径
  if (head === null) return true;
  // root是空节点，肯定没有路径
  if (root === null) return false;
  // 找到相同的节点，开始匹配是否有相同的路径
  if (root.val === head.val && judge(head, root)) return true;
  // 递归比较root的左右节点
  return isSubPath(head, root.left) || isSubPath(head, root.right);
}
// @lc code=end
